/**
 * 排序数组
 * @param {number[]} nums
 * @return {number[]}
 */
var sortArray = function (nums) {
  const N = nums.length;
  let temp = new Array();
  mergeSort(nums, 0, N - 1, temp);
  return nums;
};

/**
 * 归并排序
 * @param {number[]} nums
 * @param {number} left
 * @param {number} right
 * @param {number[]} temp
 * @returns
 */
var mergeSort = function (nums, left, right, temp) {
  // 如果指针重叠了就返回
  if (left >= right) {
    return;
  }

  // let mid = Math.floor(left + (right - left) / 2);
  let mid = (left + right) >> 1;
  // 递归调用mergeSort
  mergeSort(nums, left, mid, temp);
  mergeSort(nums, mid + 1, right, temp);
  // 归并两个有序数组
  merge(nums, left, mid, right, temp);
};

/**
 * 归并两个有序数组
 * @param {number[]} nums
 * @param {number} left
 * @param {number} mid
 * @param {number} right
 * @param {number[]} temp
 */
var merge = function (nums, left, mid, right, temp) {
  // 将nums复制到temp中去
  for (let k = left; k <= right; k++) {
    temp[k] = nums[k];
  }

  // 给两个数组分别定义一个指针
  let i = left;
  let j = mid + 1;

  // 将temp中的元素按规则写回nums
  for (let k = left; k <= right; k++) {
    if (i > mid) {
      // 左半边取尽，取右半边元素
      nums[k] = temp[j];
      j++;
    } else if (j > right) {
      // 右半边取尽，取左半边元素，左指针右移
      nums[k] = temp[i];
      i++;
    } else if (temp[i] <= temp[j]) {
      // 谁小就取谁 ，左边小
      nums[k] = temp[i];
      i++;
    } else {
      // 右边小
      nums[k] = temp[j];
      j++;
    }
  }
};

let arr = sortArray([3, 4, 2, 1]);
console.log(arr);